import java.util.ArrayList;
import java.util.List;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2023-06-25
 * Time: 22:46
 */
public class Solution {
        public int divide(int a, int b) {
            // 考虑被除数为最小值的情况
            if (a == Integer.MIN_VALUE) {
                if (b == 1) {
                    return Integer.MIN_VALUE;
                }
                if (b == -1) {
                    return Integer.MAX_VALUE;
                }
            }
            // 考虑除数为最小值的情况
            if (b == Integer.MIN_VALUE) {
                return a == Integer.MIN_VALUE ? 1 : 0;
            }
            // 考虑被除数为 0 的情况
            if (a == 0) {
                return 0;
            }
            
            // 一般情况，使用类二分查找
            // 将所有的正数取相反数，这样就只需要考虑一种情况
            boolean rev = false;
            if (a > 0) {
                a = -a;
                rev = !rev;
            }
            if (b > 0) {
                b = -b;
                rev = !rev;
            }
            
            List<Integer> candidates = new ArrayList<Integer>();
            candidates.add(b);
            int index = 0;
            // 注意溢出
            while (candidates.get(index) >= a - candidates.get(index)) {
                candidates.add(candidates.get(index) + candidates.get(index));
                ++index;
            }
            int ans = 0;
            for (int i = candidates.size() - 1; i >= 0; --i) {
                if (candidates.get(i) >= a) {
                    ans += 1 << i;
                    a -= candidates.get(i);
                }
            }
            
            return rev ? -ans : ans;
        }
    }
